package simple.tree;

import struct.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/diameter-of-binary-tree/">543. 二叉树的直径</a>
 * 给你一棵二叉树的根节点，返回该树的 直径 。
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
 * 两节点之间路径的 长度 由它们之间边数表示。
 * 示例 1：
 *   输入：root = [1,2,3,4,5]
 *   输出：3
 *   解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
 * 示例 2：
 *   输入：root = [1,2]
 *   输出：1
 * 提示：
 *   树中节点数目在范围 [1, 10^4] 内
 *   -100 <= Node.val <= 100
 * @author 刘学松
 * @date 2023-05-31 15:34
 */
public class 二叉树的直径 {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int left = dfs(node.left);
        int right = dfs(node.right);
        max = Math.max(max, left + right);
        return Math.max(left, right) + 1;
    }
}
